//反转链表
class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        // prev <- cur next
        ListNode* prev=nullptr;
        ListNode* cur=head;
        while(cur)
        {
            ListNode* next=cur->next;
            cur->next=prev;
            prev=cur;
            cur=next;
        }
        return prev;
    }
};
//反转链表II
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) 
    {
        ListNode *pphead=new ListNode(-1);
        pphead->next=head;
        ListNode* p1=pphead,*p2=pphead,*p3=pphead,*p4=pphead;
        for(int i=1;i<left;i++)
        {
            p1=p1->next;
        }
        p2=p1->next;
        for(int i=0;i<right;i++)
        {
            p3=p3->next;
        }
        p4=p3->next;
        p3->next=nullptr;
        //p1  [p2     p3]  p4 接下来要反转p2到p3这部分链表
        ListNode*prev=p4;
        ListNode* cur=p2;
        while(cur)
        {
            ListNode* tmp=cur->next;
            cur->next=prev;
            prev=cur;
            cur=tmp;
        }
        p1->next=p3;
        return pphead->next;
    }
};

//重排链表
class Solution {
public:
    void reorderList(ListNode* head) 
    {
        //把节点全部放入链表，一次取前面的一次取后面的
        vector<ListNode*>v;
        if(head==nullptr) return;
        ListNode* cur=head;
        while(cur)
        {
            v.push_back(cur);
            cur=cur->next;
        }
        cur=head;
        int count=1;
        //一开始--count=0时，从前面取的，所以约定
        //i为偶数次 从前面取 ， i为奇数次 从后面取
        int i=1;int j=v.size()-1;
        while(i<=j)
        {
            if(count%2==1)
            {
                cur->next=v[j];
                j--;
                cur=cur->next;
            }
            else
            {
                cur->next=v[i];
                i++;
                cur=cur->next;
            }
            count++;
        }
        cur->next=nullptr;
    }
};

//查找共用字符
class Solution {
public:
    vector<string> commonChars(vector<string>& words) 
    {
        //我们需要将 每个字符出现的哈希映射存下来
        //对比这些哈希映射 每个字符都选取最小的
        //此时就得到了 每个字符串都出现的共用字符
        int hash[26]={0};//这个hash用于存放共用字符的哈希映射的最小次数
        int tmphash[26]={0};//用于存放其他字符串的哈希映射

        //先用 words[0]初始化hash
        string w1=words[0];
        for(int i=0;i<w1.size();i++)
        {
            hash[w1[i]-'a']++;
        }
        for(int i=1;i<words.size();i++)
        {
            memset(tmphash,0,sizeof tmphash);
            for(int j=0;j<words[i].size();j++)
            {
                tmphash[words[i][j]-'a']++;
            }
            for(int k=0;k<26;k++)
            {
                hash[k]=min(hash[k],tmphash[k]);
            }
        }
        vector<string>res;
        for(int i=0;i<26;i++)
        {
            while(hash[i])
            {
                string tmp(1,'a'+i);
                res.push_back(tmp);
                hash[i]--;
            }
        }
        return res;
    }
};

//长按键入
class Solution {
public:
    bool isLongPressedName(string name, string typed) 
    {
        int i=0,j=0;
        if(name[0]!=typed[0]) return false;
        while(i<name.size() && j<typed.size())
        {
            if(name[i]==typed[j])
            {
                i++;
                j++;
            }
            else
            {
                while(j<typed.size() && typed[j]==typed[j-1])
                {
                    j++;
                }
                if(name[i]!=typed[j]) return false;
                else i++,j++;
            }
        }
        if(i<name.size()) return false;
        while(j<typed.size())
        {
            if(typed[j]==typed[j-1])
            {
                j++;
            }
            else
            {
                return false;
            }
        }
        return true;
    }
};